package lcr;

import java.util.ArrayList;
import java.util.List;

public class Test0110 {
    public static void main(String[] args) {
        new Solution_LCR0110().allPathsSourceTarget(new int[][]{{1,2},{3},{3},{}});
    }
}


class Solution_LCR0110 {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        dfs(graph,0,new ArrayList<>());
        return ans;
    }

    public void dfs(int[][] graph, int now, List<Integer> path) {
        path.add(now);
        int[] gra = graph[now];

        if (now==graph.length-1){
            ans.add(new ArrayList<>(path));
        }else {
            for (int next : gra) {
                dfs(graph, next, path);
            }
        }

        path.remove(path.size()-1);
    }
}

class Solution0110_1 {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int length1 = graph.length;
        int length2 = graph[0].length;
        List<List<Integer>> ans=new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>(length1);
        dfs(graph,0,list,ans);
        return ans;
    }

    public void dfs(int[][] graph,int now,ArrayList<Integer> list,List<List<Integer>> ans){
        list.add(now);

        if (graph.length-1==now){
            ans.add(new ArrayList<>(list));
        }else {
            int[] nexts = graph[now];
            for (int next : nexts) {
                dfs(graph,next,list,ans);
            }
        }

        list.remove(list.size()-1);
    }
}